package com.algorithm.algorithm.排序算法;


import java.util.Arrays;
//单边扫描以左边为轴实现快速排序，感觉比以右轴时好写些，不然开始i的位置不好确定
//j（快指针）可以先到轴的前面一个位置，与轴的大小经行比较，比轴小则将慢指针i往前进1与j的数据经行交换，j继续前进，j扫描到最后一个位置时候，一轮排序结束,即while循环结束
//将左轴的位置与此时i位置进行交换，此时轴的位置已经确定好，左边比轴小，右边比轴大，将左边与右边重复上述操作
public class QuickSort3 {

	public static void main(String[] args) {
		int a[]={5,2,4,5,1,3};
		QuickSort(a,0,5);
		System.out.println(Arrays.toString(a));
	}

	public static void  QuickSort(int[] a,int left,int right){
		if(left<right){
			int temp=a[left];
			int i=left;
			int j=left+1;
			while (j<=right){
				if(a[j]<=temp){
					i++;
					swap(a,i,j);
					j++;
				}else{
					j++;
				}
			}
			swap(a,i,left);
			QuickSort(a,0,i-1);
			QuickSort(a,i+1,right);
		}


	}
	public static void  swap(int a[],int left,int right){
		int temp=a[right];
		a[right]=a[left];
		a[left]=temp;
	}

}
